package newcoder.算法.冒泡排序;

/**
 * @Author Mr.wang
 * @Description
 * @Date 2020-04-11
 */
public class Main {
    /**
     * 原理：每次比较两个相邻的元素，将交大的元素交换至右端
     * 思路： 每次冒泡排序操作都会将相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足，则交换这两个相邻元素的次序，
     * 一次冒泡至少让一个元素移动到它应该排列的位置，重复N次，就完成了冒泡排序。
     * https://blog.csdn.net/NathanniuBee/article/details/83413879
     * 时间复杂度： 如果我们的数据正序，只需要走一趟即可完成排序，所需的比较次数C和记录移动次数M均达到最小值；
     * 即：Cmin = n-1；Mmin =0；所以冒泡排序最好的时间复杂度是O(n)
     * 如果数据是反序，需要进行n-1趟排序，每趟排序要进行n-i次比较（1<=i<=n-1），且每次比较都必须要移动记录三次来达到交换记录位置，
     * <p>
     * 执行的总次数为count =3(1+2+3+...+n-1),
     */

    public static void main(String[] args) {
        Integer[] arr = {2, 4, 7, 6, 8, 5, 9};
        bubbleSort(arr, arr.length);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
    }

    public static void bubbleSort(Integer[] arr, int n) {
        // 如果只有一个元素就不用了排序
        if (n <= 1) return;

        // 外层循环控制比较轮数（n轮）
        for (int i = 0; i < n; i++) {
            boolean didSwap = false;
            // 内层循环控制每轮比较次数，-1是为了防止arr[j + 1]的时候数组越界
            for (int j = 0; j < n - 1 - i; j++) {
                // 这两个相邻的数是逆序的，交换，得到从小到大排列
                if (arr[j] > arr[j + 1]) {
                    // 最差的情况，执行n-1次
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    didSwap = true;
                }
            }
            if (!didSwap) return;
        }
    }

}
